package myutil.mylist;

import java.util.Comparator;
import java.util.Iterator;

/**
 *
 * @author Hlib_Babii
 */
public class MyCollections {
    /**
     * sorts the list in ascending order
     * @param <T>
     * @param list list to be sorted
     */
    public static <T extends Comparable<? super T>> void sort(MyList<T> list){
        if (list.size() <= 1) {
            return;
        }
        if (list instanceof RandomAccess) {
            quickSort(list, 0, list.size() - 1, null);
        } else {
            bubbleSort(list, null);
        }
    } 
    
    /**
     * Sorts the list in ascending order using the specified comparator
     * @param <T>
     * @param list list to be sorted
     * @param c comparator for elements in the list
     */
    public static <T> void sort(MyList<T> list, Comparator<? super T> c){
        if (list.size() <= 1) {
            return;
        }
        if (list instanceof RandomAccess) {
            quickSort(list, 0, list.size() - 1, c);
        } else {
            bubbleSort(list, c);
        }
    } 
    
    /**
     *  Swaps the elements at the specified positions in the specified list
     * @param <T>
     * @param list
     * @param i
     * @param j 
     */
    public static <T> void swap(MyList<T> list, int i, int j){
        T tmp = list.get(i);
        list.set(i, list.get(j));
        list.set(j, tmp);
    }
    
    /**
     * Copies all of the elements from one list into another. After the
     * operation, the index of each copied element in the destination list
     * will be identical to its index in the source list.  The destination
     * list must be at least as long as the source list. 
     * @param <T>
     * @param dest list to copy into
     * @param src list to copy from
     * @exception MyIndexOutOfBoundsException when {@code src} is longer
     * than {@code dest}
     */
    public static <T> void copy(MyList<? super T> dest, MyList<? extends T> src) {
        if (src.size() > dest.size()) {
            throw new MyIndexOutOfBoundsException();
        }
        if (dest instanceof RandomAccess) {
            Iterator<? extends T> it = src.iterator();
            for (int i = 0; i < src.size(); i++) {
                dest.set(i, it.next());
            }
        } else {
            Iterator<? super T> it = dest.iterator();
            for (int i = 0; i < src.size(); i++) {
                it.next();
                it.remove();
            }
            dest.addAll(0, (T[])src.toArray());
        }
    }
    
    /**
     * Reverses the order of the elements in the specified list
     * @param <T>
     * @param list list to be reversed
     */
    public static <T> void reverse(MyList<T> list){
        if (list instanceof RandomAccess) {
            int listSize = list.size();
            for (int i = 0; i < listSize >> 1; i++)
            swap(list, i, listSize - 1 -i);
        } else {
            T[] array = (T[]) list.toArray();
            list.clear();
            for (int i = array.length - 1; i >= 0; i--) {
                list.add(array[i]);
            }
        }
    }
    
    /**
     * ASSUME LIST IS SORTED
     *  - реализует рекурсивный поиск в отсортированном массиве методом бисекции. Если элемент найден, то возвращается его индекс. 
     * Если не найден, то возвращается отрицательное значение, вычисляемое по следующей формуле: 
     * (-(insertion point) - 1), где insertion point - индекс того места в массиве, где должен был бы быть указанный элемент.
     * @param <T>
     * @param list the list to find element in
     * @param key element to be found in the list
     * @return 
     * @throws ClassCastException if elements of the {@code list}
     * don't implement Comparable
     */
    public static <T> 
            int binarySearch(RandomAccess list, T key) {
        MyList<? extends Comparable<? super T>> castedList;
        castedList = (MyList<? extends Comparable<? super T>>)list;    
                
        if (castedList.isEmpty()) {
            return -1;
        } else {
            return binarySearchFromTo(castedList, key, 0, castedList.size());
        }
    }

    /**
     * Implements quick sort on the specified list
     * @param list
     * @param from
     * @param to
     * @param c 
     */
    private static <T> void quickSort(MyList<T> list, 
            int from, int to, Comparator<? super T> c) {
        int left = from;
        int right = to;
        T centerValue = list.get((left + right) >> 1);
        while (left <= right) {
            while (compare(list.get(left), centerValue, c) < 0) {
                ++left;
            }
            while (compare(list.get(right), centerValue, c) > 0) {
                --right;
            }
            if (left <= right) {
                swap(list, left, right);
                ++left;
                --right;
            }
        }
        if (right > from) {
            quickSort(list, from, right, c);
        }
        if (left < to) {
            quickSort(list, left, to, c);
        }
    }

    /**
     * Implements bubble sort on the specified list
     * @param list list to be sorted
     * @param c comparator to be used
     */
    private static <T> void bubbleSort(MyList<T> list,
                                    Comparator<? super T> c) {
        T[] array = (T[]) list.toArray();
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (compare(array[j], array[j+1], c) > 0) {
                    T tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                }
            }
        }
        list.clear();
        list.addAll(array);
    }
    
    /**
     * Compares two objects by calling Comparator#compare if c != null,
     * otherwise objects being compared must implement Comparable
     * interface.
     * @param obj1
     * @param obj2
     * @param c
     * @return 
     */
    private static <T> int compare(T obj1, T obj2, Comparator<? super T> c) {
        if (c == null) {
            // assert (obj1 instanceof Comparable) && (obj2 instanceof Comparable);
            Comparable comp1 = (Comparable) obj1;
            Comparable comp2 = (Comparable) obj2;
            return comp1.compareTo(comp2);
        } else {
            return c.compare(obj1, obj2);
        }
    }

    private static <T> int binarySearchFromTo 
                    (MyList<? extends Comparable<? super T>> list, 
                            T key, int from, int to) {

        if (to - from == 1) {
            Comparable<? super T> listElm = list.get(from);
            if (listElm.equals(key)) {
                return from;
            } else {
                return (compare(key, listElm, null) < 0) ? -from-1 : -to-1;
            }
        }
        int center = (from + to) / 2;
        int compResult = list.get(center).compareTo(key);
        if (compResult == 0) {
            return center;
        } else if (compResult < 0) {
            return binarySearchFromTo(list, key, center + 1, to);
        } else {
            return binarySearchFromTo(list, key, from, center);            
        }
    }
}
